Diseño Y Análisis De Algoritmos

1 Contenido de la clase

¿Cómo se mide la complejidad de un algoritmo? [01:30-02:01]

La complejidad se mide según el número de pasos (operaciones) elementales que el algoritmo tiene que ejecutar [01:30-01:39]. Como primer ejemplo se toma la ordenación: para ordenar n números hay que comparar elementos de a pares, y el número de comparaciones necesarias es, básicamente, del orden de n² (n al cuadrado) [01:55-02:01].

Planteamiento del problema del intervalo de suma máxima [02:19-03:10]

Hay una lista de n números. Hace falta encontrar dos indicadores (dos índices: dónde empieza y dónde termina el segmento) de modo que, al sumar los elementos de ese intervalo, la suma sea lo más grande posible; el profesor llama a ese resultado "el intervalo de mayor peso" [02:19-02:35]. El ejemplo que se trabaja en toda la clase es una lista de calificaciones de un examen: 10, 15, −20, 40, −10, −20, 30, 40 [02:45-03:10].

Calentamiento: el máximo por división y conquista [03:18-03:46]

Antes de atacar el problema se muestra una técnica de base: para hallar el número más grande de la lista se puede dividir la lista en dos, encontrar el máximo de cada sublista y quedarse con el mayor de los dos [03:18-03:28]. Con los 8 números del ejemplo, las dos mitades dan 15 y 40, y el máximo es 40 [03:40-03:46].

Solución ingenua: probar todos los intervalos [05:55-06:12]

La primera idea es probar todas las posibilidades: tomar todos los intervalos de tamaño n y calcular su suma, luego todos los de tamaño n−1, n−2, y así hasta los de cualquier tamaño, y quedarse con el de mayor suma ("agarrar el mejor") [05:55-06:10]. Como cada intervalo queda determinado por su primer y último elemento, el número total de intervalos es la combinación de n tomados de a 2:

C(n,2) = n(n−1) / 2

[09:43-09:52, 21:42]. Si además hay que volver a sumar cada intervalo desde cero, el trabajo total es del orden de n², igual que en el ejemplo de la ordenación.

Acelerar con sumas parciales (prefijos) [26:37-26:53]

En lugar de recalcular cada suma desde cero, se calculan las sumas parciales desde el principio (los prefijos de la lista): 10; 10+15=25; 25−20=5; 5+40=45; y así sucesivamente hasta 85 [26:41-26:53]. Con estos prefijos, la suma de un intervalo se obtiene en un solo paso:

suma(i..j) = prefijo[j] − prefijo[i−1]

Por ejemplo, si el intervalo llega hasta el final (prefijo 85) y empieza justo después del prefijo mínimo 5, su peso es 85 − 5 = 80 [48:23-48:28, 67:07].

El algoritmo lineal: seguir el prefijo mínimo [61:22-68:00]

La pregunta clave que guía la solución es: "si sé que el intervalo termina acá, ¿dónde empieza?" [48:37-48:42]. La respuesta: empieza justo después de la posición donde el prefijo acumulado es el más pequeño hasta ese punto. Entonces, mientras se avanza por la lista, se va comparando y guardando el prefijo mínimo visto hasta ahora [61:43-61:47]; el peso del mejor intervalo que termina en la posición i es prefijo[i] − prefijo mínimo anterior. El profesor hace el recorrido con los números negativos del ejemplo: −10+40=30 y al comparar con −10 queda −10; luego −10−10=−20 y el mínimo sigue en −10; después −20−20=−40 y el mínimo pasa a −40, etc. [63:12-64:24]. El resultado para el ejemplo es el intervalo 40, −10, −20, 30, 40, cuya suma 80 es la mayor posible [48:23-48:28].

Contar operaciones y orden de complejidad [47:12-47:54, 65:45-68:00]

Medir la complejidad es contar el número de operaciones básicas que se hacen [65:49-65:56]. Con un polinomio como ejemplo —algo del tipo n³ + n⁴ + n log n—, el orden lo impone el término de mayor grado: sería del orden de n⁴ [47:12-47:35]. Aplicado al problema de la clase, el método de "todas las parejas" tiene una complejidad del tamaño del número de parejas, es decir, O(n²) [67:14-67:26], mientras que el método del prefijo mínimo es lineal, O(n) [27:25-27:35].

Organización del curso [44:55-46:40]

El profesor adelanta que va a crear unas páginas donde los estudiantes subirán las tareas y donde serán calificadas [44:55-45:15]. [parte no entendida — nombre de la plataforma y detalles de contacto]. El resto de la explicación de la logística queda ininteligible en la grabación.

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

En esta clase no se dejó ninguna tarea concreta con fecha de entrega. El profesor únicamente adelantó la mecánica por venir y conviene repasar lo explicado:

[parte no entendida — plataforma y forma de contacto mencionadas por el profesor]

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

El profesor no citó libros, páginas ni herramientas concretas en esta clase. Recursos útiles para profundizar lo explicado:

6 Glosario de términos

• Complejidad de un algoritmo: medida del costo de un algoritmo, expresada según el número de pasos u operaciones elementales que ejecuta.
• Paso/operación elemental: la unidad de trabajo básica (comparación, suma, asignación) que se cuenta para medir la complejidad.
• Orden de complejidad: notación asintótica (p. ej. O(n²), O(n)) que describe cómo crece el costo según el tamaño n de la entrada.
• Ordenación: problema de poner una lista en orden; requiere comparar elementos de a pares (del orden de n² comparaciones).
• Intervalo / subarreglo contiguo: segmento consecutivo de la lista, definido por un primer y un último índice.
• Peso del intervalo: la suma de los elementos que contiene el intervalo.
• Suma parcial / prefijo: suma acumulada desde el inicio de la lista hasta una posición.
• Prefijo mínimo: el menor valor de las sumas parciales registrado hasta un punto; marca dónde debe empezar el mejor intervalo.
• Combinación C(n,2): número de parejas de índices que se pueden escoger de n elementos: n(n−1)/2.
• División y conquista: técnica que divide el problema en subproblemas (p. ej. la lista en dos mitades), los resuelve y combina resultados.
• Algoritmo de Kadane: nombre estándar de la solución lineal O(n) al problema de la suma máxima, equivalente al método del prefijo mínimo descrito en clase.

7 Mapa mental textual

• Diseño y Análisis de Algoritmos · Clase 1
  • Medir la complejidad: contar pasos elementales
    • Ordenar n números → O(n²) comparaciones
    • Polinomio → manda el término de mayor grado (n³ + n⁴ + n log n → O(n⁴))
  • Problema del intervalo de suma máxima
    • Lista ejemplo: 10, 15, −20, 40, −10, −20, 30, 40 (calificaciones)
    • Soluciones:
      • Fuerza bruta: todos los intervalos → C(n,2) = n(n−1)/2 → O(n²)
      • Sumas parciales (prefijos): suma(i..j) = prefijo[j] − prefijo[i−1]
      • Lineal O(n): guardar el prefijo mínimo → peso = prefijo[i] − prefijo mínimo
    • Resultado del ejemplo: intervalo 40, −10, −20, 30, 40 → suma máxima 80
  • Organización del curso: subir tareas a las páginas del profesor (calificadas) [44:55-45:15]